 class Solution {
    public int numIslands(char[][] grid) {
        visited = new boolean[grid.length][grid[0].length];
        int ans = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    dfs(grid, i, j);
                    ans++;
                }
            }
        }
        return ans;
    }
    private void bfs(char[][] grid, int sx, int sy) {
        Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair(sx, sy));
        visited[sx][sy] = true;
        while (!queue.isEmpty()) {
            Pair<Integer, Integer> pair = queue.poll();
            int x = pair.getKey();
            int y = pair.getValue();
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx < 0 || ny < 0 || nx >= grid.length || ny >= grid[0].length) {
                    continue;
                }
                if (grid[nx][ny] == '1' && !visited[nx][ny]) {
                    queue.offer(new Pair(nx, ny));
                    visited[nx][ny] = true;
                }
            }
        }
    }
    private void dfs(char[][] grid, int x, int y) {
        if (visited[x][y] || grid[x][y] == '0') {
            return;
        }
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= grid.length || ny >= grid[0].length) {
                continue;
            }
            if (grid[nx][ny] == '1' && !visited[nx][ny]) {
                dfs(grid, nx, ny);
            }
        }
    }
    private int[] dx = {0, 1, 0, -1};
    private int[] dy = {1, 0, -1, 0};
    private boolean[][] visited;
}
